package list;

/**
 * 206. 反转链表（较多场景会用）
 * 链表双指针写法
 *
 * @author Api
 * @date 2023/10/6 12:21
 */
public class Code206_ReverseLinkedList {
    // 双指针写法(必须写会)
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null; // 反转后尾节点为null
        while (cur != null) {
            ListNode temp; // 定义临时temp，为保存cur的下一个节点
            temp = cur.next; // 定义临时temp，为保存cur的下一个节点
            cur.next = pre; // 将cur的下一个节点设置为pre
            pre = cur; // pre设置为cur节点
            cur = temp; // cur设置为原cur的下一个节点
        }
        return pre;
    }

    // 递归写法
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        return reverse(head, null);
    }

    private static ListNode reverse(ListNode cur, ListNode pre) {
        // 终止条件
        if (cur == null) {
            return pre;
        }
        ListNode temp;
        temp = cur.next;
        cur.next = pre;
        return reverse(temp, cur);
    }

    // 从后面向前递归
    public ListNode reverseList3(ListNode head) {
        // 边缘条件判断
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList3(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的head节点为尾节点，next需要指向null;
        head.next = null;
        return last;
    }


    // 链表写法
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}




